﻿//https://leetcode.cn/problems/spiral-matrix/?envType=problem-list-v2&envId=array

class Solution {
    //顺时针各个方向上的旋转，以及下一个位置的计算
    int dir[4][4] = { {0,1},{1,0},{0,-1},{-1,0} };
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        if (n == 0 || m == 0)
        {
            return {};
        }

        int total = m * n;
        vector<vector<bool>> vist(m, vector<bool>(n));
        vector<int> ret(total);
        int row = 0, col = 0, dirIndex = 0;
        for (int i = 0; i < total; i++)
        {
            //把当前位置加入结果，并修改访问标记
            ret[i] = matrix[row][col];
            vist[row][col] = true;
            //获取下一个位置
            int nextrow = row + dir[dirIndex][0], nextcol = col + dir[dirIndex][1];
            //判断下一个位置是否合法，不合法需要旋转方向
            if (nextrow < 0 || nextrow >= m || nextcol < 0 || nextcol >= n || vist[nextrow][nextcol])
            {
                dirIndex = (dirIndex + 1) % 4;
            }
            //修改不合法位置至合法
            row += dir[dirIndex][0];
            col += dir[dirIndex][1];
        }
        return ret;
    }
};
